package com.stephen.data.sort;

import java.util.Arrays;

/**
 * @author: stephen
 * @create: 2020-01-31 16:06
 * @description: 选择排序,比冒泡排序快很多
 */
public class SelectSort {

    static int[] arr = {0,10,-1,2};
    // -1,10,0,2
    // -1,0,10,2
    // -1,0,2,10

    public static void main(String[] args) {
        System.out.println(Arrays.toString(arr));
        System.out.println("排序后");
        System.out.println(Arrays.toString(sort(arr)));

        // 测试排序速度
        // 创建一个80000个随机数的数组
        int[] arrTest = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arrTest[i] = (int)(Math.random() * 80000000);
        }

        long start = System.nanoTime();
        sort(arrTest); // 2秒
        long end = System.nanoTime();
        System.out.printf("排序用时为[%d]秒",(end - start)/1_000_000_000);

    }

    /**
     * 先假定第一个最小,然后依次与后边比较,如果有更小的,先记录,
     * 等到本轮循环结束,如果本轮第一个元素不是最小,则与最小值交换位置
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr) {
        // 总循环次数是 arr.length - 1
        for (int i = 0; i < arr.length - 1; i++) {
            // 每一轮中都假定本轮中,第一个值最小
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min < arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 当最小值的位置跟预想的不一样时,才进行交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        return arr;
    }
}
